System Fibonacciego

System Fibonacciego to binarny, pozycyjny system liczbowy, w którym poszczególnym pozycjom odpowiadają kolejne liczby Fibonacciego.

W zapisie liczby nie używa się pierwszych dwóch liczb z ciągu Fibonacciego (czyli zera i pierwszej z dwóch występujących w nim jedynek). Zaczynającemu się od 1 ciągowi cyfr 0 i 1 (tylko takich się używa) a_na_n-1...a₂ odpowiada liczba a_n⋅F_n + a_n-1⋅F_n-1 + ... + a₂⋅F₂.

Na przykład liczba zapisana w systemie Fibonacciego jako 1000_F oznacza piątą liczbę w ciągu Fibonacciego czyli 5,

• 1000101_F = F₈+F₄+F₂ = 21+3+1 = 25
• 10010010_F = F₉+F₆+F₃ = 34+8+2 = 44

Taki sposób zapisu liczb nie byłby jednoznaczny (np. 100_F = 11_F), więc dodaje się wymaganie, by kolejne dwie liczby nie były jednocześnie jedynkami (dwie jedynki zastępujemy jedną na wcześniejszym miejscu …011… = …100…). W ten sposób otrzymujemy jednoznaczny zapis każdej liczby naturalnej.

Modyfikacje

Kompresja

W systemie Fibonacciego jedynkę zawsze poprzedza zero (z wyjątkiem pierwszego wyrazu) możemy zatem dopisać na początku zero i zastąpić pary cyfr 01 przez 1. Skracamy w ten sposób zapis liczby o tyle cyfr ile było jedynek poza pierwszą w standardowym kodzie.

Kod Fibonacciego

W systemie Fibonacciego nigdy dwie jedynki nie występują na kolejnych miejscach, możemy zatem kolejne dwie jedynki uznać za dodatkowy symbol końca liczby. Daje nam to sposób zapisu ciągu liczb. W kodzie Fibonacciego liczby zapisujemy w porządku odwrotnym niż w systemie Fibonacciego i każdą z liczb kończymy jedynką. Przy odczytywaniu drugą z jedynek w parze traktujemy jako znak końca liczby.

Przykład

• 1000_F = 5
• 1000101_F = 25
• 10010010_F = 44

„Odwracamy liczby” i otrzymujemy:

• 0001
• 1010001
• 01001001

Dopisujemy jedynki:

• 00011
• 10100011
• 010010011

Łączymy i otrzymujemy binarny ciąg 0001110100011010010011 kodujący ciąg liczb 5, 25, 44.